Feature #8: Similarity Measure Between DNA Samples

Description#

The DNA of an alien species consists of a sequence of nucleotides, where each nucleotide is represented by a letter. We received two such DNA samples, and we need to measure the extent of similarity—also known as the edit distance—between them. The prevalent measure of similarity between these two samples is the minimum number of edits that are required to convert one DNA sample to the other.

Note: We are only permitted to insert, delete, or update a nucleotide in a DNA sample.

Given two DNA samples as strings, sample1 and sample2, we have to return the minimum number of operations that are required to convert sample1 to sample2.

The following examples may clarify this problem:

Solution#

We’ll compare the sample1 string with the sample2 string, one character at a time. If the characters at the current position match, then no edit operation will be required.

On the other hand, if the characters at the current position in the two strings don’t match, we can perform one of the following three operations, whichever will result in the fewest edit operations:

• Insert a character to sample1 at the current position.
• Delete the character in sample1 at the current position.
• Replace the character in sample1 at the current position with the character at the current position in sample2.

The choice shown above can’t be made on the basis of local optimality. The actual cost of all of the choices given above must consider the edit cost for matching the rest of the characters in sample1 with the rest of the characters in sample2.

Let’s look at an example where we compare sample1 = abcdef with sample2 = azced. If we start the comparison on the first characters of the two strings, a, there will be a match. The second characters of the two strings are b and z, respectively. Over here, we can perform one of these three operations:

• If we insert z into sample1, then we must find the edit distance between the strings bcdef and ced.
• If we replace b with z, then we must find the edit distance between the strings cdef and ced.
• If we delete the character b, then we must find the edit distance between the strings cdef and zced.

Once we’ve considered all of these options, we must return the minimum number of edit operations that are required to convert sample1 to sample2. This will lead to a recursive problem formulation, which has several overlapping subproblems and optimal substructure. Therefore, we will solve this problem using dynamic programming.

We will use the concept of memoization, where we use an array to store the already solved subproblems. We have to match all the nucleotides of the two samples that are given. For this, we can use a 2D array to store the edit distances. Let’s call this array D, whose size is defined by n and m, the lengths of sample1 and sample2, respectively.

The value in D[i][j] will represent the edit distance between the substrings formed by the first i nucleotides of sample1 and the first j nucleotides of sample2. To compute the edit distance D[i][j], we can perform the following three edit operations:

• Delete: D[i-1][j],
• Insert: D[i][j-1],
• Replace: D[i-1][j-1]

We also need to take care of a couple of cases to compute the edit distance, D[i][j]:

• If the nucleotide at sample1[i] matches the nucleotide at sample2[j]:

  $D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1]-1)$

• If the nucleotide at sample1[i] does not match the nucleotide at sample2[j]:

  $D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1])$

Based on these computations, we will compute an edit distance D[i][j] like this:

We also have a couple of base cases, which are as follows:

• If sample2 is empty, we can remove all the nucleotides of sample1 to make it empty too, that is, D[i][0] = i.

• If sample1 is empty, we have to insert all the nucleotides of sample2 into sample1, D[0][j] = i.

Now that we know the base cases and the general formulas used to compute an edit distance D[i][j], we can look at the computation steps in the illustration below:

Let’s look at the code for this solution:

Complexity measures#

Let $n$ and $m$ be the number of nucleotides in sample1 and sample2, respectively.

Time complexity#

Since we are using an array that stores the results for all the subproblems, we can conclude that we will not have more than $n*m$ subproblems. Therefore, the time complexity will be $O(n*m)$.

Space complexity#

The algorithm will use $O(n*m)$ space for the array.